/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: GodK
 * Date: 2024-03-20
 * Time: 22:16
 */
public class Main {
    public static void getNext(int[] next,String sub){
        int k = 0;
        int i = 2;
        next[0] = -1;
        next[1] = 0;
        while(i<sub.length()){
            if(k==-1||sub.charAt(i-1)==sub.charAt(k)){
                next[i] = k + 1;
                k++;
                i++;
            }else{
                k = next[k];
            }
        }
    }
    public static int KMP(String str,String sub,int pos){
        if (str==null||sub==null)return -1;
        int lenstr = str.length();
        int lensub = sub.length();
        if (lenstr==0||lensub==0)return -1;
        if (pos<0||pos>=lenstr)return -1;
        int i = pos;
        int j = 0;
        int[] next = new int[sub.length()];
        getNext(next,sub);
        while(i<lenstr&&j<lensub){
            if(j==-1||str.charAt(i+1)==sub.charAt(j)){
                i++;
                j++;
            }else{
                j=next[j];
            }
        }
        if(j>=lensub){
            return i-j;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(KMP("abcdeasdgujkyak","ak",0));
        System.out.println(KMP("abcdeasdgujkyk","yk",0));

    }
}
